package mo.tags.backtrack.classify;

import java.util.ArrayList;
import java.util.List;

public class L46 {

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> combination = new ArrayList<>();
        int len = nums.length;
        boolean[] visited = new boolean[len];
        dfs(res, combination, nums, 0, len, visited);
        return res;
    }

    private void dfs(List<List<Integer>> res, List<Integer> combination, int[] nums, int idx, int len, boolean[] visited) {
        if (combination.size() == len) {
            res.add(new ArrayList<>(combination));
            return;
        }
        for (int i = 0; i < len; i++) {
            if (!visited[i]) {
                combination.add(nums[idx]);
                visited[i] = true;
                dfs(res, combination, nums, idx+1, len, visited);
                combination.remove(combination.size()-1);
                visited[i] = false;
            }
        }



    }


    public static void main(String[] args) {
        L46 test = new L46();
        System.out.println(test.permute(new int[]{1, 2, 3}));
    }
}
